package com.LeeCode;

import java.util.Arrays;

/**
 * 矩阵区域和
 */

public class Code1314 {
    public static void main(String[] args) {
        int[][] mat = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        int k = 1;
        System.out.println(Arrays.deepToString(new Code1314().matrixBlockSum(mat, k)));
    }

    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] preSum = new int[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                preSum[i + 1][j + 1] = mat[i][j] + preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j];
            }
        }

        int[][] ans = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int r1 = Math.max(0, i - k), r2 = Math.min(m - 1, i + k);
                int c1 = Math.max(0, j - k), c2 = Math.min(n - 1, j + k);
                ans[i][j] = preSum[r2 + 1][c2 + 1] - preSum[r1][c2 + 1] - preSum[r2 + 1][c1] + preSum[r1][c1];
            }
        }
        return ans;
    }
}
